package sort;

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
	public static void main(String[] args) {
		int[] arr = {9,7,6,5,4,3,2,1,55,99,88,77,66,55,44,22,33,11};
		bucketSort(arr);
	}

	public static  void bucketSort(int[] arr){
		int max = Integer.MIN_VALUE;
		//故意搞反，保证区间在Integer范围内
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max,arr[i]);
			min = Math.min(min,arr[i]);
		}

		//桶数
		int bucketNum = (max - min)/arr.length +1;
		ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
		for (int i = 0; i < bucketNum; i++) {
			bucketArr.add(new ArrayList<>());
		}

		//将每个元素放入桶中
		for (int i = 0; i < arr.length; i++) {
			int num = (arr[i] - min)/(arr.length);
			bucketArr.get(num).add(arr[i]);
		}

		ArrayList result = new ArrayList(arr.length);
		//对每个桶进行排序
		for (int i=0;i<bucketArr.size();i++){
			ArrayList<Integer> integers = bucketArr.get(i);
			Collections.sort(integers);
			result.addAll(integers);
		}
		System.out.println(result.toString());
	}
}
